The present invention relates to circuitry for detecting and correcting errors in data words occurring in Reed-Solomon (RS) coded blocks. The circuitry comprises a stage that constructs syndromes (defined hereinafter) in the data flowing through the blocks; a stage that detects erasures in the syndromes; a stage that applies a Euclid's algorithm with EQU T.sub.s (x)={Q.sub.s-1 (x).multidot.T.sub.s-1 (x)}+T.sub.s-2 (x), EQU R.sub.s (x)={Q.sub.s-1 (x).multidot.R.sub.s-1 (x)}+R.sub.s-2 (x),
and EQU Q.sub.s-2 (x)=R.sub.s-2 (x)/R.sub.s-1 (x),
wherein T.sub.s (x) , R.sub.s (x) , and Q.sub.s-1 (x) are polynomials representing the position of the error, its value, and a provisional value respectively, and wherein R.sub.s (x) and T.sub.s (x) can be normalized with a minimal coefficient T.sub.s (0)=.delta. such that R(x)=R.sub.s (x)/.delta. and T(x)=T.sub.s (x)/.delta.; a stage that detects error positions X.sub.k and values Y.sub.K by conducting a Chien zero-root search in conjunction with ##EQU2## wherein T' (X.sub.k) is the first derivative of T at a place X.sub.k ; and a stage that uses the accordingly calculated error positions X.sub.k and values Y.sub.K to correct signal-duration matched data words in a currently present Reed-Solomon coded block. A Reed-Solomon code is a systematic block code of length n wherein n-k=p checkwords are applied to k information symbols. The coding does not alter communications symbols. A Reed-Solomon code has a minimal Hamming distance d=p+1, that can be freely selected to detect and correct errors.
Decoding does not differentiate between data words and checkwords. A Reed-Solomon code block consists of n symbols, each of one or more bits. A symbol width of 8 bits is usually the starting point. 2.multidot.t checkwords are usually needed in correcting a symbol error t to calculate its position X.sub.i and value Y.sub.i. If the defective symbol is marked as an erasure, its error position X.sub.i will be known. In this event only a single checkword will be needed to calculate error value Y.sub.i. In Reed-Solomon codes, 2t+e .ltoreq.P=n-k=d-1, wherein i is the number of erasures. Further details on Reed-Solomon codes can be found in "On-the-Fly Decoder for Multiple Byte Errors," IBM Journal of Research and Development, vol. 30, No. 3 (May 1986), pp. 259-69.
Circuitry for decoding Reed-Solomon coded data is known from "A 40 MHz Encoder/Decoder Chip Generated by a Reed-Solomon Code Compiler," IEEE 1990 Custom Integrated Circuits Conference, CH2860-5/90/0000-0065, pp. 13.5.1-13.5.4. One stage calculates syndromes from the data received in a transmission section. A downstream stage calculates the polynomial error positions and values from the calculated syndrome in accordance with Euclid's algorithm. The results are subjected to a Chien zero-root search in a third stage. The resulting positions and values are employed in a fourth stage to correct the occurring data with an exclusive OR.
Such circuitry cannot be employed to correct a large number of errors in real time.